package leetcode.weekly.week324;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

//Solution3Test
public class Solution3 {

	public boolean isPossible(int n, List<List<Integer>> edges) {
		int[] ins = new int[n + 1];
		List<Integer>[] e = new ArrayList[n + 1];
		for (int i = 0; i < e.length; i++) {
			e[i] = new ArrayList();
		}
		for (List<Integer> list : edges) {
			int a = list.get(0), b = list.get(1);
			ins[a]++;
			ins[b]++;
			e[a].add(b);
			e[b].add(a);
		}
		List<Integer> odd = new ArrayList<>();
		boolean ep = false;
		for (int i = 0; i < ins.length; i++) {
			int num = ins[i];
			if ((num & 1) == 1) {
				odd.add(i);
			} else {
				if (num < n - 1) {
					ep = true;
				}
			}
		}
		if ((odd.size() & 1) == 1 || odd.size() > 4) {
			return false;
		}
		if (odd.size() == 0) {
			return true;
		}
		if (odd.size() == 2) {
			if (!e[odd.get(0)].contains(odd.get(1))) {
				return true;
			}
			int x = odd.get(0), y = odd.get(1);
			for (int i = 1; i <= n; ++i)
				if (i != x && i != y && !e[i].contains(x) && !e[i].contains(y))
					return true;
			return false;
			// return ins[odd.get(0)] < n - 1 && ins[odd.get(1)] < n - 1;// 这个逻辑真的没想全，这是必要条件，但是不充分
			// e[odd.get(0)][odd.get(1)] == 0
		}
		if (!e[odd.get(0)].contains(odd.get(1)) && !e[odd.get(2)].contains(odd.get(3))) {
			return true;
		}
		if (!e[odd.get(0)].contains(odd.get(2)) && !e[odd.get(1)].contains(odd.get(3))) {
			return true;
		}
		if (!e[odd.get(0)].contains(odd.get(3)) && !e[odd.get(1)].contains(odd.get(2))) {
			return true;
		}
		return false;
	}
}
